#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>



//#define DEBUG


typedef unsigned char u8;



/*
    Matchstick binary definition:

    number:
             _        1
            | |     1 0 1
    0 ->    |_|     1 1 1   0b01101111(0x6f)

                      0
              |     0 0 1
    1 ->      |     0 0 1   0b00001001(0x09)

             _        1
             _|     0 1 1
    2 ->    |_      1 1 0   0b01011110(0x5e)

             _        1
             _|     0 1 1
    3 ->     _|     0 1 1   0b01011011(0x5b)

                      0
            |_|     1 1 1
    4 ->      |     0 0 1   0b00111001(0x39)

             _        1
            |_      1 1 0
    5 ->     _|     0 1 1   0b01110011(0x73)


             _        1
            |_      1 1 0
    6 ->    |_|     1 1 1   0b01110111(0x77)

             _        1
              |     0 0 1
    7 ->      |     0 0 1   0b01001001(0x49)

             _        1
            |_|     1 1 1
    8 ->    |_|     1 1 1   0b01111111(0x7f)

             _        1
            |_|     1 1 1
    9 ->     _|     0 1 1   0x01111011(0x7b)

    Sign:
    + ->    +       1 1     0x11111111(0xff)

    - ->    -       0 1     0x11111101(0xfd)

    Equal
    = ->    =       spc     0x10000000(0x80)
*/



#define BINARY_MAX (10)
#define TABLE_MAX (20)


typedef enum {
    BI_TYPE_UNKNOWN,
    BI_TYPE_NUMBER,
    BI_TYPE_SIGN,
    BI_TYPE_SIGN_EQ,
}bi_type_t;

static const u8 s_number_0 = 0x6f;
static const u8 s_number_1 = 0x09;
static const u8 s_number_2 = 0x5e;
static const u8 s_number_3 = 0x5b;
static const u8 s_number_4 = 0x39;
static const u8 s_number_5 = 0x73;
static const u8 s_number_6 = 0x77;
static const u8 s_number_7 = 0x49;
static const u8 s_number_8 = 0x7f;
static const u8 s_number_9 = 0x7b;

static const u8 s_sign_eq = 0x80;
static const u8 s_sign_plus = 0xff;
static const u8 s_sign_minus = 0xfd;

static const u8 s_bi_sign_mask = 0xfc;
static const u8 s_bi_sign_eq_mask = 0x80;
static const u8 s_bi_number_mask = 0x80;

static char s_question_table[TABLE_MAX][BINARY_MAX];
static int s_question_table_len = 0;



static void generate_equation(char *eq);
static void make_all_questions(int moves, char *answer_str);
static bi_type_t check_type(u8);
static bool eq2bi(u8 *bi_list, int *len, const char *eq);
static bool bi2eq(char *eq, const u8 *bi_list, const int len);
static int get_popcount(u8);
static void recursive_traverse_move(
    int moves,
    const u8 *step_binary_list, const int step_binary_list_len,
    int answer_moves,
    const u8 *answer_binary_list, const int answer_binary_list_len);
static void get_target_index_list_by_mask(u8 *list, int *len, u8 data, u8 mask, u8 target);
static void get_take_away_index_list(u8 *list, int *len, u8 data);
static void get_put_in_index_list(u8 *list, int *len, u8 data);
static void get_number_take_away_index_list(u8 *list, int *len, u8 data);
static void get_sign_take_away_index_list(u8 *list, int *len, u8 data);
static void get_number_put_in_index_list(u8 *list, int *len, u8 data);
static void get_sign_put_in_index_list(u8 *list, int *len, u8 data);
static void move_matchstick(
    u8 *tmp_binary_list, int *tmp_binary_list_len,
    const u8 *src_binary_list, const int len,
    const int src, const int src_index,
    const int drt, const int drt_index);
static int diff_binary_list(const u8 *step_binary_list, const int step_binary_list_len, const u8 *answer_binary_list, const int answer_binary_list_len);
static bool check_duplicate(char *question_str);



int main()
{
    char answer_equation_str[10];

    srand((unsigned)time(NULL));

    generate_equation(answer_equation_str);
    //strcpy(answer_equation_str, "2+3=5");

    printf("Input number for moves:\r\n");
    int moves = 0;

    scanf("%d", &moves);
    //moves = 2;

    printf("Move %d matchsticks:\r\n", moves);
    make_all_questions(moves, answer_equation_str);
    printf("Answer: %s\r\n", answer_equation_str);

    return 0;
}

void generate_equation(char *eq)
{
    int c = rand() % 10;       // 0~9
    int a = rand() % (c + 1);  // 0~c
    int b = c - a;             // b>0
    sprintf(eq, "%d+%d=%d", a, b, c);
}

void make_all_questions(int moves, char *answer_str)
{
    bool rs = false;
    u8 answer_binary_list[BINARY_MAX];

    memset(answer_binary_list, 0, sizeof(answer_binary_list));

    int len = 0;
    rs = eq2bi(answer_binary_list, &len, answer_str);

#ifdef DEBUG
    printf("eq2bi(%s): ", (rs?"true":"false"));
    for (int i = 0; i < len; ++i) {
        printf("0x%x ", answer_binary_list[i]);
    }
    printf("\r\n");
#endif

    recursive_traverse_move(
        moves, answer_binary_list, len,
        moves, answer_binary_list, len);
}

bi_type_t check_type(u8 bi)
{
    if ((bi & s_bi_sign_mask) == s_bi_sign_mask) {
        return BI_TYPE_SIGN;
    }

    if ((bi & s_bi_sign_eq_mask) == s_bi_sign_eq_mask) {
        return BI_TYPE_SIGN_EQ;
    }

    if ((bi & s_bi_number_mask) == 0) {
        return BI_TYPE_NUMBER;
    }

    return BI_TYPE_UNKNOWN;
}

bool eq2bi(u8 *bi_list, int *len, const char *eq)
{
    *len = 0;
    int slen = strlen(eq);
    if (slen == 0) {
        return false;
    }
    for (int i = 0; i < slen; ++i) {
        u8 bi = 0;
        char c = eq[i];
        switch(c) {
        case '0':
            bi = s_number_0;
            break;
        case '1':
            bi = s_number_1;
            break;
        case '2':
            bi = s_number_2;
            break;
        case '3':
            bi = s_number_3;
            break;
        case '4':
            bi = s_number_4;
            break;
        case '5':
            bi = s_number_5;
            break;
        case '6':
            bi = s_number_6;
            break;
        case '7':
            bi = s_number_7;
            break;
        case '8':
            bi = s_number_8;
            break;
        case '9':
            bi = s_number_9;
            break;
        case '+':
            bi = s_sign_plus;
            break;
        case '-':
            bi = s_sign_minus;
            break;
        case '=':
            bi = s_sign_eq;
            break;
        default:
            return false;
        }
        bi_list[(*len)] = bi;
        (*len)++;
    }
    return true;
}

bool bi2eq(char *eq, const u8 *bi_list, const int len)
{
    int slen = 0;
    if (len == 0) {
        eq[0] = 0;
        return false;
    }
    for (int i = 0; i < len; ++i) {
        char c = '\0';
        u8 bi = bi_list[i];
        if (s_number_0 == bi) {
            c = '0';
        } else if (s_number_1 == bi) {
            c = '1';
        } else if (s_number_2 == bi) {
            c = '2';
        } else if (s_number_3 == bi) {
            c = '3';
        } else if (s_number_4 == bi) {
            c = '4';
        } else if (s_number_5 == bi) {
            c = '5';
        } else if (s_number_6 == bi) {
            c = '6';
        } else if (s_number_7 == bi) {
            c = '7';
        } else if (s_number_8 == bi) {
            c = '8';
        } else if (s_number_9 == bi) {
            c = '9';
        } else if (s_sign_plus == bi) {
            c = '+';
        } else if (s_sign_minus == bi) {
            c = '-';
        } else if (s_sign_eq == bi) {
            c = '=';
        } else {
            eq[0] = 0;
            return false;
        }
        eq[slen] = c;
        ++slen;
    }
    eq[slen] = 0;
    return true;
}

int get_popcount(u8 data)
{
    return __builtin_popcount(data & 0xff);
}

void recursive_traverse_move(
    int moves,
    const u8 *step_binary_list, const int step_binary_list_len,
    int answer_moves,
    const u8 *answer_binary_list, const int answer_binary_list_len)
{
    bool rs = false;
    u8 take_away_index_list[7];
    u8 put_in_index_list[7];
    int take_away_index_list_len = 0;
    int put_in_index_list_len = 0;
    u8 next_binary_list[BINARY_MAX];
    int next_binary_list_len = 0;
    char question_str[BINARY_MAX];

    if (moves == 0) {
        rs = bi2eq(question_str, step_binary_list, step_binary_list_len);
#ifdef DEBUG
        printf("bi2eq(%s): %s\r\n", (rs?"true":"false"), question_str);
#endif
        if (!rs) {
            return;
        }

        int diff = diff_binary_list(step_binary_list, step_binary_list_len, answer_binary_list, answer_binary_list_len);
        if (2*answer_moves != diff) {
            return;
        }

        if (check_duplicate(question_str)) {
            return;
        }

        printf("Question: %s\r\n", question_str);

        return;
    }

    for (int src = 0; src < step_binary_list_len; ++src) {
        for (int drt = 0; drt < step_binary_list_len; ++drt) {
            get_take_away_index_list(take_away_index_list, &take_away_index_list_len, step_binary_list[src]);
            get_put_in_index_list(put_in_index_list, &put_in_index_list_len, step_binary_list[drt]);
#ifdef DEBUG
            printf("take_away_index_list_len=%d\r\n", take_away_index_list_len);
            printf("put_in_index_list_len=%d\r\n", put_in_index_list_len);
#endif
            for (int i = 0; i < take_away_index_list_len; ++i) {
                for (int j = 0; j < put_in_index_list_len; ++j) {
#ifdef DEBUG
                    printf("[%d:%d]->[%d:%d]\r\n", src, take_away_index_list[i], drt, put_in_index_list[j]);
#endif
                    move_matchstick(
                        next_binary_list, &next_binary_list_len,
                        step_binary_list, step_binary_list_len,
                        src, take_away_index_list[i], drt, put_in_index_list[j]);

                    recursive_traverse_move(
                        moves - 1,
                        next_binary_list, next_binary_list_len,
                        answer_moves,
                        answer_binary_list, answer_binary_list_len);
                }
            }
        }
    }
}

void get_take_away_index_list(u8 *list, int *len, u8 data)
{
    switch(check_type(data)) {
    case BI_TYPE_NUMBER:
        get_number_take_away_index_list(list, len, data);
        break;
    case BI_TYPE_SIGN:
        get_sign_take_away_index_list(list, len, data);
        break;
    case BI_TYPE_SIGN_EQ:
    case BI_TYPE_UNKNOWN:
    default:
        *len = 0;
        return;
    }
}

void get_put_in_index_list(u8 *list, int *len, u8 data)
{
    switch(check_type(data)) {
    case BI_TYPE_NUMBER:
        get_number_put_in_index_list(list, len, data);
        break;
    case BI_TYPE_SIGN:
        get_sign_put_in_index_list(list, len, data);
        break;
    case BI_TYPE_SIGN_EQ:
    case BI_TYPE_UNKNOWN:
    default:
        *len = 0;
        return;
    }
}

void get_target_index_list_by_mask(u8 *list, int *len, u8 data, u8 mask, u8 target)
{
    int blen = get_popcount(~mask);
    *len = 0;
#ifdef DEBUG
    printf("data=0x%x, list:\r\n", data);
#endif
    for (int i = 0; i < blen; ++i) {
        if ((((data >> i)) & 0x01) == target) {
            list[*len] = i;
            ++(*len);
#ifdef DEBUG
            printf("%d\r\n", i);
#endif
        }
    }
}

void get_number_take_away_index_list(u8 *list, int *len, u8 data)
{
    get_target_index_list_by_mask(list, len, data, s_bi_number_mask, 0x01);
}

void get_sign_take_away_index_list(u8 *list, int *len, u8 data)
{
    get_target_index_list_by_mask(list, len, data, s_bi_sign_mask, 0x01);
}

void get_number_put_in_index_list(u8 *list, int *len, u8 data)
{
    get_target_index_list_by_mask(list, len, data, s_bi_number_mask, 0x00);
}

void get_sign_put_in_index_list(u8 *list, int *len, u8 data)
{
    get_target_index_list_by_mask(list, len, data, s_bi_sign_mask, 0x00);
}


void move_matchstick(
    u8 *tmp_binary_list, int *tmp_binary_list_len,
    const u8 *src_binary_list, const int len,
    const int src, const int src_index,
    const int drt, const int drt_index)
{
    memcpy(tmp_binary_list, src_binary_list, len);
    *tmp_binary_list_len = len;
    tmp_binary_list[src] &= ~(0x01<<src_index); //take away
    tmp_binary_list[drt] |= (0x01<<drt_index);  //put in
}

int diff_binary_list(const u8 *step_binary_list, const int step_binary_list_len, const u8 *answer_binary_list, const int answer_binary_list_len)
{
    if (step_binary_list_len != answer_binary_list_len) {
        return 0;
    }

    u8 a = 0;
    u8 b = 0;
    u8 diff = 0;
    u8 count = 0;

    for (int i = 0; i < answer_binary_list_len; ++i) {
        a = step_binary_list[i] & (~s_bi_number_mask);
        b = answer_binary_list[i] & (~s_bi_number_mask);
        diff = a ^ b;
        count += get_popcount(diff);
    }

    return count;
}

bool check_duplicate(char *question_str)
{
    if (s_question_table_len >= TABLE_MAX) {
        return true;
    }

    for (int i = 0; i < s_question_table_len; ++i) {
        if (strcmp(s_question_table[i], question_str) == 0) {
            return true;
        }
    }
    strcpy(s_question_table[s_question_table_len], question_str);
    ++s_question_table_len;
    return false;
}

